#
# @lc app=leetcode.cn id=1049 lang=python
#
# [1049] 最后一块石头的重量 II
#

# @lc code=start
class Solution(object):
    def lastStoneWeightII(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        total_sum = sum(stones)
        if total_sum % 2 != 0:
            last_weight = 1
        else:
            last_weight = 0
        
        dp = [0] * (total_sum//2+1)
        for weight in stones:
            for i in range(total_sum//2, weight-1, -1):
                dp[i] = max(dp[i], dp[i-weight]+weight)
        return last_weight + (total_sum//2 - dp[-1])*2
        
# @lc code=end

